Deduplication backup systems, such as EMC's Data Domain systems, use deduplication to perform backup that store much less data on backup server. Instead of copying the same data over and over again from the protected device to the backup server, deduplication backup systems first identify whether pieces of the protected data have already been backed up. If so, that piece of protected data does not need to be sent over the network from the protected device to the backup server. Instead, a reference or a virtual copy is performed from one location on backup storage to another location on backup storage. It would be desirable to reduce the backup times by improving the speed at which duplicate information is recognized and/or to reduce the amount of network traffic. Although deduplication backup systems offer faster backup times, it would be desirable if the performance of current deduplication backup systems could be further improved. It would also be desirable if such improvements could be implemented in a manner that requires relatively few changes to current deduplication backup systems.